package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: data_structures_algorithms
 * @description: 组合之和（可以重复）
 * @author: lld
 * @create: 2021-04-24 18:44
 **/
class CombinationSum39 {
    public static void main(String[] args) {
        CombinationSum39 combinationSum39 = new CombinationSum39();
        int[] arr = {1, 2, 3, 5};
        List<List<Integer>> lists = combinationSum39.combinationSum(arr, 8);
        System.out.println(lists);
    }

    List<List<Integer>> list = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> clist = new ArrayList<>();
        // 不需要判断是否访问，可以重复
        // boolean[] visited=new boolean[candidates.length];
        // 0代表从数组第一个元素开始
        dfs(candidates, clist, target, 0);
        return list;
    }

    public void dfs(int[] candidates, List<Integer> clist,
                    int target, int begin) {
        // target<0的情况可能出现，返回
        if (target < 0) return;
        if (target == 0) {
            list.add(new ArrayList<>(clist));
            return;
        }
        for (int i = begin; i < candidates.length; i++) {
            clist.add(candidates[i]);
            target -= candidates[i];
// 注意：由于每一个元素可以重复使用，下一轮搜索的起点依然是 i，这里非常容易弄错
            dfs(candidates, clist, target, i);

            target += candidates[i];
            clist.remove(clist.size() - 1);
        }
    }
}
